package net.alteiar.algorithms;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import net.alteiar.images.metadata.ImageInfo;

public class FastConvexHull {
	private static XCompare POINT_COMPARATOR = new XCompare();

	public static void fillHull(ImageInfo info, Point org, int width,
			int height, int oldValue, int value) {
		int minX = org.x;
		int maxX = org.x + width;

		int minY = org.y;
		int maxY = org.y + height;

		int minBlockX = minX / info.getSquareSize();
		int maxBlockX = maxX / info.getSquareSize();

		int minBlockY = minY / info.getSquareSize();
		int maxBlockY = maxY / info.getSquareSize();

		ArrayList<Point> allPts = new ArrayList<Point>();
		for (int x = minBlockX; x < maxBlockX; ++x) {
			for (int y = minBlockY; y < maxBlockY; ++y) {
				if (info.getValue(x, y) == value) {
					allPts.add(new Point(x, y));
				}
				info.setValue(x, y, oldValue);
			}
		}

		if (allPts.size() > 2) {
			List<Point> pts = execute(allPts);

			List<Point> contour = RayCast.line(pts.get(pts.size() - 1),
					pts.get(0));

			for (int i = 0; i < pts.size() - 1; i++) {
				contour.addAll(RayCast.line(pts.get(i), pts.get(i + 1)));
			}

			RayCast.line(info, pts.get(pts.size() - 1), pts.get(0), value);
			for (int i = 0; i < pts.size() - 1; i++) {
				RayCast.line(info, pts.get(i), pts.get(i + 1), value);
			}

			Point p1 = pts.get(0);
			p1.x += 1;
			Utils.nonRecursiveFill(info, p1, oldValue, value);
		}
	}

	public static ArrayList<Point> execute(ArrayList<Point> points) {
		ArrayList<Point> result = new ArrayList<Point>();
		ArrayList<Point> xSorted = (ArrayList<Point>) points.clone();
		Collections.sort(xSorted, POINT_COMPARATOR);

		int n = xSorted.size();
		if (n < 2)
			return result;

		Point[] lUpper = new Point[n];

		lUpper[0] = xSorted.get(0);
		lUpper[1] = xSorted.get(1);

		int lUpperSize = 2;

		for (int i = 2; i < n; i++) {
			lUpper[lUpperSize] = xSorted.get(i);
			lUpperSize++;

			while (lUpperSize > 2
					&& !rightTurn(lUpper[lUpperSize - 3],
							lUpper[lUpperSize - 2], lUpper[lUpperSize - 1])) {
				// Remove the middle point of the three last
				lUpper[lUpperSize - 2] = lUpper[lUpperSize - 1];
				lUpperSize--;
			}
		}

		Point[] lLower = new Point[n];

		lLower[0] = xSorted.get(n - 1);
		lLower[1] = xSorted.get(n - 2);

		int lLowerSize = 2;

		for (int i = n - 3; i >= 0; i--) {
			lLower[lLowerSize] = xSorted.get(i);
			lLowerSize++;

			while (lLowerSize > 2
					&& !rightTurn(lLower[lLowerSize - 3],
							lLower[lLowerSize - 2], lLower[lLowerSize - 1])) {
				// Remove the middle point of the three last
				lLower[lLowerSize - 2] = lLower[lLowerSize - 1];
				lLowerSize--;
			}
		}

		for (int i = 0; i < lUpperSize; i++) {
			result.add(lUpper[i]);
		}

		for (int i = 1; i < lLowerSize - 1; i++) {
			result.add(lLower[i]);
		}

		return result;
	}

	private static boolean rightTurn(Point a, Point b, Point c) {
		return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) > 0;
	}

	private static class XCompare implements Comparator<Point> {
		@Override
		public int compare(Point o1, Point o2) {
			return (o1.x < o2.x) ? -1 : ((o1.x == o2.x) ? 0 : 1);
		}
	}
}
